package MyLinkedHashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-09-19
 * Time: 20:02
 */

/**
 * 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value)如果关键字key 已经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/lru-cache
 */

/**
 * LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？
 *
 * 按照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未使用的，然后把新开的应用放到最上面：
 * 现在你应该理解 LRU（Least Recently Used）策略了。当然还有其他缓存淘汰策略，比如不要按访问的时序来淘汰，而是按访问频率（LFU 策略）来淘汰等等，各有应用场景。本文讲解 LRU 算法策略。
 * 详解：https://mp.weixin.qq.com/s/b0YVCccJ8mFP6lI-1NiQOQ
 */

/**
 * 法二：自己手撕哈希双向链表实现LRU缓存机制
 */
public class LRUCache {
    private MyLinkedHashMap cache;
    private int cap;

    public LRUCache(int capacity) {
        cache = new MyLinkedHashMap();
        this.cap = capacity;
    }

    public int get(int key) {
        if(!cache.contains(key)) {
            return -1;
        }
        makeRecently(key);
        return cache.get(key).val;
    }

    public void put(int key, int value) {
        if(cache.contains(key)) {
            deleteKey(key);
            addRecently(key,value);
            return;
        }
        if(cap==cache.size()) {
            removeLeastRecently();
        }
        addRecently(key,value);

    }

    private void makeRecently(int key) {
        Node x = cache.get(key);
        cache.remove(x);
        cache.addLast(key, x.val);
    }
    private void addRecently(int key,int val) {
        Node x=new Node(key,val);
        cache.addLast(key,val);
    }
    private void deleteKey(int key) {
        Node x=cache.get(key);
        cache.remove(x);
    }
    private void removeLeastRecently() {
        Node deleteNode=cache.removeFirst();
        int deleteKey=deleteNode.key;
    }
}
/**
 * 法二：使用Java内置的哈希双向链表
 */
//class LRUCache {
//    int cap;
//    LinkedHashMap<Integer,Integer> cache;
//    public LRUCache(int capacity) {
//        this.cap=capacity;
//        this.cache=new LinkedHashMap<>();
//    }
//
//    public int get(int key) {
//        if(!cache.containsKey(key)) {
//            return -1;
//        }
//        makeRecently(key);
//        return cache.get(key);
//    }
//
//    public void put(int key, int value) {
//        if(cache.containsKey(key)) {
//            cache.put(key,value);
//            makeRecently(key);
//            return;
//        }
//        if(this.cap<=cache.size()) {
//            int oldKey=cache.keySet().iterator().next();
//            cache.remove(oldKey);//删除最旧的
//        }
//        cache.put(key,value);
//    }
//    public void makeRecently(int key) {
//        int val=cache.get(key);
//        cache.remove(key);
//        cache.put(key,val);
//    }
//}
